//
//  ProblemMS0803.swift
//  TestProject
//
//  Created by 毕武侠 on 2021/5/5.
//  Copyright © 2021 zhulong. All rights reserved.
//

import UIKit

/*
 面试题 08.03. 魔术索引
 魔术索引。 在数组A[0...n-1]中，有所谓的魔术索引，满足条件A[i] = i。给定一个有序整数数组，编写一种方法找出魔术索引，若有的话，在数组A中找出一个魔术索引，如果没有，则返回-1。若有多个魔术索引，返回索引值最小的一个。

 示例1:
  输入：nums = [0, 2, 3, 4, 5]
  输出：0
  说明: 0下标的元素为0
 示例2:
  输入：nums = [1, 1, 1]
  输出：1
 说明:
     nums长度在[1, 1000000]之间
     此题为原书中的 Follow-up，即数组中可能包含重复元素的版本
 */
@objcMembers class ProblemMS0803: NSObject {
    func solution() {
        print(findMagicIndexBao([0, 2, 3, 4, 5]))
        print(findMagicIndexBao([1, 1, 1]))
    }
    
    /*
     递归+二分
     */
    
    func findMagicIndex(_ nums: [Int]) -> Int {
        return findMagicIndexDi(nums, 0, nums.count-1)
    }
    func findMagicIndexDi(_ nums: [Int], _ left: Int, _ right: Int) -> Int {
        if left > right {
            return -1
        }
        let mid = left + (right - left) >> 1
        // 先查询左边的
        let leftNum = findMagicIndexDi(nums, left, mid-1)
        if leftNum != -1 {
            return leftNum
        } else if nums[mid] == mid {
            return mid
        } else {
            return findMagicIndexDi(nums, mid+1, right)
        }
    }
    
    /*
     遍历+跳跃
     i < nums[i], 例如： 0 1 5 7 8 9 10
     当i=2 nums[2]=5, 2 < 5, 说明 i<5的数据都不符合 nums[nums[5]]
     */
    func findMagicIndexBao(_ nums: [Int]) -> Int {
        var i = 0
        while i<nums.count {
            if i == nums[i] {
                return i
            } else if i < nums[i] {
                i = nums[i]
            } else {
                i += 1
            }
        }
        return -1
    }
}
